
<!DOCTYPE html>

<html lang="en">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />

    <title>Appendices &#8212; Leo 6.7.2 documentation</title>
    <link rel="stylesheet" type="text/css" href="_static/pygments.css" />
    <link rel="stylesheet" type="text/css" href="_static/classic.css" />
    <link rel="stylesheet" type="text/css" href="_static/custom.css" />
    
    <script data-url_root="./" id="documentation_options" src="_static/documentation_options.js"></script>
    <script src="_static/jquery.js"></script>
    <script src="_static/underscore.js"></script>
    <script src="_static/_sphinx_javascript_frameworks_compat.js"></script>
    <script src="_static/doctools.js"></script>
    <script src="_static/sphinx_highlight.js"></script>
    
    <script src="_static/sidebar.js"></script>
    
    <link rel="index" title="Index" href="genindex.html" />
    <link rel="search" title="Search" href="search.html" />
    <link rel="next" title="More Leo Links" href="toc-more-links.html" />
    <link rel="prev" title="Leo University" href="leo-university.html" /> 
  </head><body>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="toc-more-links.html" title="More Leo Links"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="leo-university.html" title="Leo University"
             accesskey="P">previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="leo_toc.html">Leo 6.7.2 documentation</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="">Appendices</a></li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body" role="main">
            
  <section id="appendices">
<h1>Appendices<a class="headerlink" href="#appendices" title="Permalink to this heading">¶</a></h1>
<div class="contents local topic" id="contents">
<p class="topic-title">Contents</p>
<ul class="simple">
<li><p><a class="reference internal" href="#format-of-leo-files" id="id2">Format of .leo files</a></p></li>
<li><p><a class="reference internal" href="#format-of-external-files" id="id3">Format of external files</a></p></li>
<li><p><a class="reference internal" href="#the-leonine-way-to-refactor-code" id="id4">The Leonine way to refactor code</a></p></li>
<li><p><a class="reference internal" href="#theory-of-operation-c-deletepositionsinlist" id="id5">Theory of operation: c.deletePositionsInList</a></p></li>
<li><p><a class="reference internal" href="#leoast-py" id="id6">leoAst.py</a></p>
<ul>
<li><p><a class="reference internal" href="#running-leoast-py" id="id7">Running leoAst.py</a></p>
<ul>
<li><p><a class="reference internal" href="#running-leoast-py-from-the-command-line" id="id8">Running leoAst.py from the command line</a></p></li>
<li><p><a class="reference internal" href="#running-the-code-python-programmatically" id="id9">Running the code python programmatically</a></p></li>
<li><p><a class="reference internal" href="#running-unit-tests-and-coverage-tests-programmatically" id="id10">Running unit tests and coverage tests programmatically</a></p></li>
</ul>
</li>
<li><p><a class="reference internal" href="#tokenorder-classes-theory-of-operation" id="id11">TokenOrder classes: Theory of operation</a></p>
<ul>
<li><p><a class="reference internal" href="#token-order-classes" id="id12">Token-order classes</a></p></li>
<li><p><a class="reference internal" href="#other-classes" id="id13">Other classes</a></p></li>
<li><p><a class="reference internal" href="#significant-vs-insignificant-tokens" id="id14">Significant vs insignificant tokens</a></p></li>
<li><p><a class="reference internal" href="#helping-tog-visitors" id="id15">Helping TOG visitors</a></p></li>
<li><p><a class="reference internal" href="#syncing-tokens" id="id16">Syncing tokens</a></p></li>
<li><p><a class="reference internal" href="#figures-of-merit" id="id17">Figures of merit</a></p></li>
</ul>
</li>
<li><p><a class="reference internal" href="#notable-functions-methods" id="id18">Notable functions &amp; methods</a></p>
<ul>
<li><p><a class="reference internal" href="#initing-data-structures" id="id19">Initing data structures</a></p></li>
<li><p><a class="reference internal" href="#reading-writing-files" id="id20">Reading &amp; writing files</a></p></li>
<li><p><a class="reference internal" href="#reports" id="id21">Reports</a></p></li>
<li><p><a class="reference internal" href="#updating-tokens-and-parse-trees" id="id22">Updating tokens and parse trees</a></p></li>
<li><p><a class="reference internal" href="#tokenordergenerator-init-from-file" id="id23">TokenOrderGenerator.init_from_file</a></p></li>
</ul>
</li>
<li><p><a class="reference internal" href="#maintaining-leoast-py" id="id24">Maintaining leoAst.py</a></p></li>
</ul>
</li>
<li><p><a class="reference internal" href="#unicode-reference" id="id25">Unicode reference</a></p></li>
<li><p><a class="reference internal" href="#valid-url-s" id="id26">Valid URL’s</a></p></li>
<li><p><a class="reference internal" href="#the-mulder-ream-update-algorithm" id="id27">The Mulder/Ream update algorithm</a></p>
<ul>
<li><p><a class="reference internal" href="#what-the-algorithm-does" id="id28">What the algorithm does</a></p></li>
<li><p><a class="reference internal" href="#guesses-don-t-matter" id="id29">Guesses don’t matter</a></p></li>
<li><p><a class="reference internal" href="#background-of-the-code" id="id30">Background of the code</a></p></li>
<li><p><a class="reference internal" href="#aha-the-x-sentinels-array" id="id31">Aha: the x.sentinels array</a></p></li>
<li><p><a class="reference internal" href="#strategy-proof-of-correctness" id="id32">Strategy &amp; proof of correctness</a></p></li>
<li><p><a class="reference internal" href="#summary" id="id33">Summary</a></p></li>
</ul>
</li>
<li><p><a class="reference internal" href="#why-i-like-python" id="id34">Why I like Python</a></p>
<ul>
<li><p><a class="reference internal" href="#clarity" id="id35">Clarity</a></p></li>
<li><p><a class="reference internal" href="#power" id="id36">Power</a></p></li>
<li><p><a class="reference internal" href="#safety" id="id37">Safety</a></p></li>
<li><p><a class="reference internal" href="#speed" id="id38">Speed</a></p></li>
<li><p><a class="reference internal" href="#conclusions" id="id39">Conclusions</a></p></li>
</ul>
</li>
</ul>
</div>
<section id="format-of-leo-files">
<h2><a class="toc-backref" href="#id2">Format of .leo files</a><a class="headerlink" href="#format-of-leo-files" title="Permalink to this heading">¶</a></h2>
<p>Here are the XML elements that may appear in Leo files:</p>
<dl>
<dt>&lt;?xml&gt;</dt><dd><p>Leo files start with the following line:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>&lt;?xml version=&quot;1.0&quot; encoding=&quot;UTF-8&quot;?&gt;
</pre></div>
</div>
</dd>
<dt>&lt;?xml-stylesheet&gt;</dt><dd><p>An xml-stylesheet line is option.  For example:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>&lt;?xml-stylesheet ekr_stylesheet?&gt;
</pre></div>
</div>
</dd>
<dt>&lt;leo_file&gt;</dt><dd><p>The &lt;leo_file&gt; element opens an element that contains the entire file.
&lt;/leo_file&gt; ends the file.</p>
</dd>
<dt>&lt;leo_header&gt;</dt><dd><p>The &lt;leo_header&gt; element specifies version information and other information
that affects how Leo parses the file.  For example:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">&lt;</span><span class="n">leo_header</span> <span class="n">file_format</span><span class="o">=</span><span class="s2">&quot;2&quot;</span> <span class="n">tnodes</span><span class="o">=</span><span class="s2">&quot;0&quot;</span> <span class="n">max_tnode_index</span><span class="o">=</span><span class="s2">&quot;5725&quot;</span> <span class="n">clone_windows</span><span class="o">=</span><span class="s2">&quot;0&quot;</span><span class="o">/&gt;</span>
</pre></div>
</div>
<p>The file_format attribute gives the ‘major’ format number.
It is ‘2’ for all 4.x versions of Leo.
The tnodes and clone_windows attributes are no longer used.
The max_tnode_index attribute is the largest tnode index.</p>
</dd>
<dt>&lt;globals&gt;</dt><dd><p>The globals element specifies information relating to the entire file.
For example:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">&lt;</span><span class="nb">globals</span> <span class="n">body_outline_ratio</span><span class="o">=</span><span class="s2">&quot;0.50&quot;</span><span class="o">&gt;</span>
    <span class="o">&lt;</span><span class="n">global_window_position</span> <span class="n">top</span><span class="o">=</span><span class="s2">&quot;27&quot;</span> <span class="n">left</span><span class="o">=</span><span class="s2">&quot;27&quot;</span> <span class="n">height</span><span class="o">=</span><span class="s2">&quot;472&quot;</span> <span class="n">width</span><span class="o">=</span><span class="s2">&quot;571&quot;</span><span class="o">/&gt;</span>
    <span class="o">&lt;</span><span class="n">global_log_window_position</span> <span class="n">top</span><span class="o">=</span><span class="s2">&quot;183&quot;</span> <span class="n">left</span><span class="o">=</span><span class="s2">&quot;446&quot;</span> <span class="n">height</span><span class="o">=</span><span class="s2">&quot;397&quot;</span> <span class="n">width</span><span class="o">=</span><span class="s2">&quot;534&quot;</span><span class="o">/&gt;</span>
<span class="o">&lt;/</span><span class="nb">globals</span><span class="o">&gt;</span>
</pre></div>
</div>
<ul class="simple">
<li><p>The body_outline_ratio attribute specifies the ratio of the height of the body pane to
the total height of the Leo window.
It initializes the position of the splitter separating the outline pane from the body pane.</p></li>
<li><p>The global_window_position and global_log_window_position elements
specify the position of the Leo window and Log window in global coordinates:</p></li>
</ul>
</dd>
<dt>&lt;preferences&gt;</dt><dd><p>This element is vestigial.
Leo ignores the &lt;preferences&gt; element when reading.
Leo writes an empty &lt;preferences&gt; element.</p>
</dd>
<dt>&lt;find_panel_settings&gt;</dt><dd><p>This element is vestigial.
Leo ignores the &lt;find_panel_settings&gt; element when reading.
Leo writes an empty &lt;find_panel_settings&gt; element.</p>
</dd>
<dt>&lt;clone_windows&gt;</dt><dd><p>This element is vestigial.
Leo ignores the &lt;clone_windows&gt; element when reading.
Leo no longer writes &lt;clone_windows&gt; elements.</p>
</dd>
<dt>&lt;vnodes&gt;</dt><dd><p>A single &lt;vnodes&gt; element contains nested &lt;v&gt; elements.
&lt;v&gt; elements correspond to vnodes.
The nesting of &lt;v&gt; elements indicates outline structure in the obvious way.</p>
</dd>
<dt>&lt;v&gt;</dt><dd><p>The &lt;v&gt; element represents a single vnode and has the following form:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">&lt;</span><span class="n">v</span><span class="o">...&gt;&lt;</span><span class="n">vh</span><span class="o">&gt;</span><span class="n">sss</span><span class="o">&lt;/</span><span class="n">vh</span><span class="o">&gt;</span> <span class="p">(</span><span class="n">zero</span> <span class="ow">or</span> <span class="n">more</span> <span class="n">nested</span> <span class="n">v</span> <span class="n">elements</span><span class="p">)</span> <span class="o">&lt;/</span><span class="n">v</span><span class="o">&gt;</span>
</pre></div>
</div>
<p>The &lt;vh&gt; element specifies the headline text.
sss is the headline text encoded with the usual XML escapes.
As shown above, a &lt;v&gt; element may contain nested &lt;v&gt; elements.
This nesting indicates outline structure in the obvious way.
Zero or more of the following attributes may appear in &lt;v&gt; elements:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">t</span><span class="o">=</span><span class="n">name</span><span class="o">.</span><span class="n">timestamp</span><span class="o">.</span><span class="n">n</span>
<span class="n">a</span><span class="o">=</span><span class="s2">&quot;xxx&quot;</span>
</pre></div>
</div>
<p>The t=”Tnnn” attribute specifies the &lt;t&gt; element associated with a &lt;v&gt; element.
The a=”xxx” attribute specifies vnode attributes.
The xxx denotes one or more upper-case letters whose meanings are as follows:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">C</span>       <span class="n">The</span> <span class="n">vnode</span> <span class="ow">is</span> <span class="n">a</span> <span class="n">clone</span><span class="o">.</span> <span class="p">(</span><span class="n">Not</span> <span class="n">used</span> <span class="ow">in</span> <span class="mf">4.</span><span class="n">x</span><span class="p">)</span>
<span class="n">E</span>       <span class="n">The</span> <span class="n">vnode</span> <span class="ow">is</span> <span class="n">expanded</span> <span class="n">so</span> <span class="n">its</span> <span class="n">children</span> <span class="n">are</span> <span class="n">visible</span><span class="o">.</span>
<span class="n">M</span>       <span class="n">The</span> <span class="n">vnode</span> <span class="ow">is</span> <span class="n">marked</span><span class="o">.</span>
<span class="n">T</span>       <span class="n">The</span> <span class="n">vnode</span> <span class="ow">is</span> <span class="n">the</span> <span class="n">top</span> <span class="n">visible</span> <span class="n">node</span><span class="o">.</span>
<span class="n">V</span>       <span class="n">The</span> <span class="n">vnode</span> <span class="ow">is</span> <span class="n">the</span> <span class="n">current</span> <span class="n">vnode</span><span class="o">.</span>
</pre></div>
</div>
<p>For example, a=”EM”  specifies that the vnode is expanded and is marked.</p>
<p><strong>New in 4.0</strong>:</p>
<ul class="simple">
<li><p>&lt;v&gt; elements corresponding to &#64;file nodes now contain tnodeList attributes.
The tnodeList attribute allows Leo to recreate the order in which nodes should
appear in the outline.
The tnodeList attribute is a list of gnx’s: global node indices.
See Format of external files (4.x) for the format of gnx’s.</p></li>
<li><p>Plugins and scripts may add attributes to &lt;v&gt; and &lt;t&gt; elements.
See <a class="reference external" href="writingPlugins.html">Writing plugins</a> for details.</p></li>
</ul>
</dd>
<dt>&lt;tnodes&gt;</dt><dd><p>A single &lt;tnodes&gt; element contains a non-nested list of &lt;t&gt; elements.</p>
</dd>
<dt>&lt;t&gt;</dt><dd><p>The &lt;t&gt; element represents the body text of the corresponding &lt;v&gt; element.
It has this form:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">&lt;</span><span class="n">t</span> <span class="n">tx</span><span class="o">=</span><span class="s2">&quot;&lt;gnx&gt;&quot;</span><span class="o">&gt;</span><span class="n">sss</span><span class="o">&lt;/</span><span class="n">t</span><span class="o">&gt;</span>
</pre></div>
</div>
<p>The tx attribute is required.
The t attribute of &lt;v&gt; elements refer to this tx attribute.
sss is the body text encoded with the usual XML escapes.</p>
<p><strong>New in 4.0</strong>: Plugins and scripts may add attributes to &lt;v&gt; and &lt;t&gt;
elements. See <a class="reference external" href="writingPlugins.html">Writing plugins</a> for details.</p>
</dd>
</dl>
</section>
<section id="format-of-external-files">
<h2><a class="toc-backref" href="#id3">Format of external files</a><a class="headerlink" href="#format-of-external-files" title="Permalink to this heading">¶</a></h2>
<p>This section describe the format of external files. Leo’s <a class="reference external" href="glossary.html#sentinel-lines">sentinel lines</a> are comments, and this section describes those comments.</p>
<p id="index-0">External files created by &#64;file use gnx’s in &#64;+node sentinels. Such gnx’s permanently and uniquely identify nodes. Gnx’s have the form:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="nb">id</span><span class="o">.</span><span class="n">yyyymmddhhmmss</span>
<span class="nb">id</span><span class="o">.</span><span class="n">yyyymmddhhmmss</span><span class="o">.</span><span class="n">n</span>
</pre></div>
</div>
<p>The second form is used if two gnx’s would otherwise be identical.</p>
<ul class="simple">
<li><p>id is a string unique to a developer, e.g., a git id.</p></li>
<li><p>yyyymmddhhmmss is the node’s creation date.</p></li>
<li><p>n is an integer.</p></li>
</ul>
<p>Closing sentinels are required for section references and the &#64;all and &#64;others directives, collectively known as <strong>embedding constructs.</strong> Proof: These constructs do not terminate the node in which they appear. Without a closing sentinel there would be no way to know where the construct ended and the following lines of the enclosing node began.</p>
<p>New sentinels do not include &#64;nonl or &#64;nl. As a result, body text always ends with at least one newline.</p>
<p>Here are the sentinels used by Leo, in alphabetical order. Unless otherwise noted, the documentation applies to all versions of Leo. In the following discussion, gnx denotes a gnx as described above.</p>
<dl>
<dt>&#64;&lt;&lt;</dt><dd><p>A sentinel of the form &#64;&lt;&lt;section_name&gt;&gt; represents a section reference.</p>
<p>If the reference does not end the line, the sentinel line ending
the expansion is followed by the remainder of the reference line.
This allows the Read code to recreate the reference line exactly.</p>
</dd>
<dt>&#64;&#64;</dt><dd><p>The &#64;&#64; sentinel represents any line starting with &#64; in body text
except &#64;*whitespace*, &#64;doc and &#64;others.
Examples:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">@</span><span class="nd">@nocolor</span>
<span class="o">@</span><span class="nd">@pagewidth</span> <span class="mi">80</span>
<span class="o">@</span><span class="nd">@tabwidth</span> <span class="mi">4</span>
<span class="o">@</span><span class="nd">@code</span>
</pre></div>
</div>
</dd>
<dt>&#64;afterref</dt><dd><p>Marks non-whitespace text appearing after a section references.
As of Leo 6.6, Leo no longer <em>writes</em> afterref sentinels.
However, Leo will always <em>read</em> such sentinels correctly.</p>
</dd>
<dt>&#64;+all</dt><dd><p>Marks the start of text generated by the &#64;all directive.</p>
</dd>
<dt>&#64;-all</dt><dd><p>Marks the end of text generated by the &#64;all directive.</p>
</dd>
</dl>
<p>&#64;at and &#64;doc</p>
<blockquote>
<div><p>The &#64;+doc &#64;+at sentinels indicate the start of a doc parts.</p>
</div></blockquote>
<dl>
<dt>&#64;+body <strong>(Leo 3.x only)</strong></dt><dd><p>Marks the start of body text.</p>
</dd>
<dt>&#64;-body <strong>(Leo 3.x only)</strong></dt><dd><p>Marks the end of body text.</p>
</dd>
<dt>&#64;delims</dt><dd><p>The &#64;delims directive inserts &#64;&#64;delims sentinels into the
external file. The new delimiter strings continue in effect until
the next &#64;&#64;delims sentinel <em>in the external file</em> or until the
end of the external file. Adding, deleting or changing &#64;&#64;delim
<em>sentinels</em> will destroy Leo’s ability to read the external file.
Mistakes in using the &#64;delims <em>directives</em> have no effect on Leo,
though such mistakes will thoroughly mess up a external file as
far as compilers, HTML renderers, etc. are concerned.</p>
</dd>
<dt>&#64;section-delims  (Leo 6.6+)</dt><dd><p>The &#64;section-delims directive inserts &#64;&#64;section-delims sentinels
into the external file. The directive must appear in the root
&#64;&lt;file&gt; node.</p>
</dd>
<dt>&#64;+leo</dt><dd><p>Marks the start of any external file. This sentinel has the form:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">&lt;</span><span class="n">opening_delim</span><span class="o">&gt;</span><span class="nd">@leo</span><span class="o">&lt;</span><span class="n">closing_delim</span><span class="o">&gt;</span>
</pre></div>
</div>
<p>The read code uses single-line comments if &lt;closing_delim&gt; is empty.
The write code generates single-line comments if possible.</p>
<p>The &#64;+leo sentinel contains other information. For example:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">&lt;</span><span class="n">opening_delim</span><span class="o">&gt;</span><span class="nd">@leo</span><span class="o">-</span><span class="n">ver</span><span class="o">=</span><span class="mi">4</span><span class="o">-</span><span class="n">thin</span><span class="o">&lt;</span><span class="n">closing_delim</span><span class="o">&gt;</span>
</pre></div>
</div>
</dd>
<dt>&#64;-leo</dt><dd><p>Marks the end of the Leo file.
Nothing but whitespace should follow this directive.</p>
</dd>
</dl>
<dl>
<dt>&#64;+node</dt><dd><p>Mark the start and end of a node:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">@+</span><span class="n">node</span><span class="p">:</span><span class="n">gnx</span><span class="p">:</span><span class="o">&lt;</span><span class="n">headline</span><span class="o">&gt;</span>
</pre></div>
</div>
</dd>
<dt>&#64;nonl <strong>(Leo 3.x only)</strong></dt><dd><p>Suppresses a newline in the outline.</p>
</dd>
<dt>&#64;others</dt><dd><p>The &#64;+others sentinel indicates the start of the expansion of an &#64;+others
directive, which continues until the matching &#64;-others sentinel.</p>
</dd>
<dt>&#64;verbatim</dt><dd><p>&#64;verbatim indicates that the next line of the external file is not a sentinel.
This escape convention allows body text to contain lines that would otherwise
be considered sentinel lines.</p>
</dd>
</dl>
</section>
<section id="the-leonine-way-to-refactor-code">
<h2><a class="toc-backref" href="#id4">The Leonine way to refactor code</a><a class="headerlink" href="#the-leonine-way-to-refactor-code" title="Permalink to this heading">¶</a></h2>
<p>This paper explains how to use cff (clone-find-flattened) while
refactoring code. I could not have completed the refactoring of Leo’s
atFile write code without using continuous, extensive use of cff.</p>
<p>There are two key ideas:</p>
<ol class="arabic simple">
<li><p>The clones produced by cff are short-term or medium-term data,
easily created and easily dispensed with.</p></li>
</ol>
<p>Such clones are valuable, but not precious. They will eventually be discarded.</p>
<ol class="arabic simple" start="2">
<li><p>Unlike tags (or any other kind of non-Leonine data), the clones
produced by cff can be reorganized.</p></li>
</ol>
<p>This is the priceless, unique advantage of clones.  You don’t understand clones if you don’t get this.</p>
<p>Example</p>
<ol class="arabic simple">
<li><p>While refactoring, it is essential to see all actual uses of a
symbol (method, or ivar, whatever).</p></li>
</ol>
<p>The starting point is to use cff to find all potential uses of the
symbol. If multiple files or classes use the symbol, you can use the
suboutline-only option to limit the matches created by cff.</p>
<ol class="arabic simple" start="2">
<li><p>After finding all potential uses of the symbol, you can reorganize
the resulting clones as follows:</p></li>
</ol>
<ul class="simple">
<li><p>Delete nodes that are completely irrelevant.</p></li>
<li><p>Squirrel away likely-irrelevant nodes in a new organizer node.</p></li>
<li><p>Highlight the defining node, say by making it the preceding sibling of the cff node.</p></li>
<li><p>Leave all actual uses of the symbol where they are.</p></li>
</ul>
<ol class="arabic simple" start="3">
<li><p>You have now focused your attention on the nodes that will likely
change.</p></li>
</ol>
<p>You can now rerun the search only on those cloned nodes to see all
instances of the symbol that might be changed. This is a crucial
double check on proposed changes.</p>
<p>Summary</p>
<p>I highly recommend that all Leonine programmers use the approach just
described when refactoring code.</p>
<p>Neither tags, nor filters, nor refactoring packages can emulate the
Leonine way of refactoring.</p>
</section>
<section id="theory-of-operation-c-deletepositionsinlist">
<h2><a class="toc-backref" href="#id5">Theory of operation: c.deletePositionsInList</a><a class="headerlink" href="#theory-of-operation-c-deletepositionsinlist" title="Permalink to this heading">¶</a></h2>
<p>The positions passed to p.deletePositionsInList only <em>specify</em> the desired
changes; the only way to <em>make</em> those changes is to operate on vnodes!</p>
<p>Consider this outline, containing no clones:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">+</span> <span class="n">ROOT</span>
  <span class="o">-</span> <span class="n">A</span>
  <span class="o">-</span> <span class="n">B</span>
</pre></div>
</div>
<p>The fundamental problem is this. If we delete node A, the index of
node B in ROOT.children will change. This problem has (almost) nothing
to do with clones or positions.</p>
<p><strong>Proof that c.deletePositionsInList is correct</strong></p>
<p>Clearly, deleting a positions ultimately means changing vnodes,
specifically, v.parents and v.children for v in some set of vnodes. We must
show that the particular set of changed vnodes in the new code is the
correct set of vnodes, and that the changes made to that set are correct.
This is far from obvious at first glance.</p>
<p><strong>The new code</strong></p>
<p>Here is Vitalije’s version of c.deletePositionsInList, without the docstring:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">deletePositionsInList</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">aList</span><span class="p">):</span>
    <span class="n">c</span> <span class="o">=</span> <span class="bp">self</span>

    <span class="c1"># Ensure all positions are valid.</span>
    <span class="n">aList</span> <span class="o">=</span> <span class="p">[</span><span class="n">p</span> <span class="k">for</span> <span class="n">p</span> <span class="ow">in</span> <span class="n">aList</span> <span class="k">if</span> <span class="n">c</span><span class="o">.</span><span class="n">positionExists</span><span class="p">(</span><span class="n">p</span><span class="p">)]</span>
    <span class="k">if</span> <span class="ow">not</span> <span class="n">aList</span><span class="p">:</span>
        <span class="k">return</span>

    <span class="k">def</span> <span class="nf">p2link</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
        <span class="n">parent_v</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="n">stack</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="k">if</span> <span class="n">p</span><span class="o">.</span><span class="n">stack</span> <span class="k">else</span> <span class="n">c</span><span class="o">.</span><span class="n">hiddenRootNode</span>
        <span class="k">return</span> <span class="n">p</span><span class="o">.</span><span class="n">_childIndex</span><span class="p">,</span> <span class="n">parent_v</span>

    <span class="n">links_to_be_cut</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">p2link</span><span class="p">,</span> <span class="n">aList</span><span class="p">)),</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span><span class="o">-</span><span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>

    <span class="c1"># The main loop.</span>
    <span class="k">for</span> <span class="n">i</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">links_to_be_cut</span><span class="p">:</span>
        <span class="n">child_v</span> <span class="o">=</span> <span class="n">v</span><span class="o">.</span><span class="n">children</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
        <span class="n">child_v</span><span class="o">.</span><span class="n">parents</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">v</span><span class="p">)</span>
</pre></div>
</div>
<p>To begin the proof, note that the main loop has the expected “form”. That
is, when we delete a node, we will:</p>
<ol class="arabic simple">
<li><p>Delete child_v = v.children[i] for some v and i.</p></li>
<li><p>Delete child_v from its parents array.</p></li>
</ol>
<p>v.parents is an unordered array, so child_v.parents.remove(v) is all that
is needed. This line might crash if one of the positions is invalid. It
will also crash if v is not present in child_v.parents. I’ll discuss this
later.</p>
<p>To complete the proof, we must show that the main loop deletes all and only
those vnodes implied by the positions in aList. We can tentatively assume
that the main loop will work properly if that data in links_to_be_cut is
correct, but there are some subtleties lurking here which I’ll discuss later.</p>
<p>The following code creates links_to_be_cut:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">p2link</span><span class="p">(</span><span class="n">p</span><span class="p">):</span>
    <span class="n">parent_v</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="n">stack</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="k">if</span> <span class="n">p</span><span class="o">.</span><span class="n">stack</span> <span class="k">else</span> <span class="n">c</span><span class="o">.</span><span class="n">hiddenRootNode</span>
    <span class="k">return</span> <span class="n">p</span><span class="o">.</span><span class="n">_childIndex</span><span class="p">,</span> <span class="n">parent_v</span>

<span class="n">links_to_be_cut</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">p2link</span><span class="p">,</span> <span class="n">aList</span><span class="p">)),</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span><span class="o">-</span><span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">])</span>
</pre></div>
</div>
<p>This is elegant (compressed) code. Let’s examine it carefully…</p>
<p>p2link produces tuples (childIndex, parent_v). These become bound to i, v
in the main loop:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="c1"># The main loop.</span>
<span class="k">for</span> <span class="n">i</span><span class="p">,</span> <span class="n">v</span> <span class="ow">in</span> <span class="n">links_to_be_cut</span><span class="p">:</span>
    <span class="n">child_v</span> <span class="o">=</span> <span class="n">v</span><span class="o">.</span><span class="n">children</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
    <span class="n">child_v</span><span class="o">.</span><span class="n">parents</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">v</span><span class="p">)</span>
</pre></div>
</div>
<p>To make this work, parent_v must be the vnode whose i’th child should be
deleted:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">parent_v</span> <span class="o">=</span> <span class="n">p</span><span class="o">.</span><span class="n">stack</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span> <span class="k">if</span> <span class="n">p</span><span class="o">.</span><span class="n">stack</span> <span class="k">else</span> <span class="n">c</span><span class="o">.</span><span class="n">hiddenRootNode</span>
</pre></div>
</div>
<ul class="simple">
<li><p>p.stack entries have the form (v, childIndex), so p.stack[-1] is the
position p’s immediate parent vnode, if p has a parent. Otherwise,
c.hiddenRootNode is the proper parent vnode.</p></li>
<li><p>p._childIndex is also the correct value for i.</p></li>
</ul>
<p>We have just proved the following:</p>
<blockquote>
<div><p><em>Deleting position p means executing the main loop for (i, v) returned by p2link(p).</em></p>
</div></blockquote>
<p><strong>Sorting and filtering</strong></p>
<p>The following line filters and sorts the results produced by p2link:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">links_to_be_cut</span> <span class="o">=</span> <span class="nb">sorted</span><span class="p">(</span><span class="nb">set</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">p2link</span><span class="p">,</span> <span class="n">aList</span><span class="p">)),</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span><span class="o">-</span><span class="n">x</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
</pre></div>
</div>
<p>Let’s break this into parts, from “inside” to “outside”</p>
<ul class="simple">
<li><p>map(p2link, aList) applies p2link to every position in aList.
The result is a list of tuples (i, v). It may contain duplicates.</p></li>
<li><p>set(map(p2link, aList) removes those duplicates.
Let <strong>theSet</strong> be set(map(p2link, aList).</p></li>
<li><p>Finally, sorted(theSet, key=lambda x:-x[0]) creates a generator
equivalent to a sorted list.</p></li>
</ul>
<p>The generator will deliver the tuples (i, v) in descending order of i, when
several tuples (i, v) have the same vnode. The generator does not order
tuples on v, and there is no need to do so.</p>
<p>It’s easy to understand the intent of this sort order. The main loop
contains this line:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">child_v</span> <span class="o">=</span> <span class="n">v</span><span class="o">.</span><span class="n">children</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
</pre></div>
</div>
<p>The sort order means that pop(i) happens before pop(j) if i &gt; j. This
ensures that the precomputed values of i won’t change in the main loop.</p>
<p><strong>Completing the proof</strong></p>
<p>The algorithm appears sound. The tuples (i, v) computed from p2link(p)
correctly describe the work to be done. Filtering ensures that the work is
done once. Sorting ensures that child indices i will not change during the
main loop.</p>
<p>The (i, v) tuples are sorted on i, but not v. aList can contain positions
in any order, so we know only that for any particular vnode v the main loop
will handle tuples (i1, v), (i2, v), … in the correct order.</p>
<p>There are two final questions to consider:</p>
<p>First, does the order in which the main loop handles vnodes matter?</p>
<p>No. The vnode data are independent. The main loop works regardless of
whether a vnode has already been unlinked.</p>
<p>Second, could the following lines ever fail?</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">child_v</span> <span class="o">=</span> <span class="n">v</span><span class="o">.</span><span class="n">children</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
<span class="n">child_v</span><span class="o">.</span><span class="n">parents</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">v</span><span class="p">)</span>
</pre></div>
</div>
<p>No. Sorting and filtering ensure that (i, v) are unique. v is guaranteed to
be in child_v.parents because v.children[i] must exist.</p>
<p>This concludes the proof.</p>
<p><strong>Discussion</strong></p>
<p>The algorithm is sound because the tuples (i, v) contain no duplicates. For
any particular v, the main loop will process the set of tuples (i, v) in
descending order of i. This resolves the question of whether deleting
already deleted positions is valid.</p>
</section>
<section id="leoast-py">
<h2><a class="toc-backref" href="#id6">leoAst.py</a><a class="headerlink" href="#leoast-py" title="Permalink to this heading">¶</a></h2>
<p>The classes in <a class="reference external" href="https://github.com/leo-editor/leo-editor/blob/devel/leo/core/leoAst.py">leoAst.py</a>
unify python’s token-based and ast-based worlds by creating two-way links
between tokens in the token list and ast nodes in the parse tree.</p>
<p>leoAst.py is part of <a class="reference external" href="https://leo-editor.github.io/leo-editor/">Leo</a>, and can be used
completely independently of Leo.</p>
<p>You must use Leo to see the intended outline structure of the code. Without
Leo, you will see special <strong>sentinel comments</strong> that create Leo’s outline
structure. These comments have the form:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="c1">#@&lt;comment-kind&gt;:&lt;user-id&gt;.&lt;timestamp&gt;.&lt;number&gt;: &lt;outline-level&gt; &lt;headline&gt;</span>
</pre></div>
</div>
<p>If you have any trouble installing or using this code, please help for help
on <a class="reference external" href="https://groups.google.com/forum/#!forum/leo-editor">Leo’s forum</a></p>
<section id="running-leoast-py">
<h3><a class="toc-backref" href="#id7">Running leoAst.py</a><a class="headerlink" href="#running-leoast-py" title="Permalink to this heading">¶</a></h3>
<section id="running-leoast-py-from-the-command-line">
<h4><a class="toc-backref" href="#id8">Running leoAst.py from the command line</a><a class="headerlink" href="#running-leoast-py-from-the-command-line" title="Permalink to this heading">¶</a></h4>
<p>leoAst.py is designed to be run from the command line:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">usage</span><span class="p">:</span>
    <span class="n">leoAst</span><span class="o">.</span><span class="n">py</span> <span class="o">--</span><span class="n">help</span>
    <span class="n">leoAst</span><span class="o">.</span><span class="n">py</span> <span class="p">[</span><span class="o">--</span><span class="n">fstringify</span> <span class="o">|</span> <span class="o">--</span><span class="n">fstringify</span><span class="o">-</span><span class="n">diff</span> <span class="o">|</span> <span class="o">--</span><span class="n">orange</span> <span class="o">|</span> <span class="o">--</span><span class="n">orange</span><span class="o">-</span><span class="n">diff</span><span class="p">]</span> <span class="n">PATHS</span>
    <span class="n">leoAst</span><span class="o">.</span><span class="n">py</span> <span class="o">--</span><span class="n">py</span><span class="o">-</span><span class="n">cov</span> <span class="p">[</span><span class="n">ARGS</span><span class="p">]</span>
    <span class="n">leoAst</span><span class="o">.</span><span class="n">py</span> <span class="o">--</span><span class="n">pytest</span> <span class="p">[</span><span class="n">ARGS</span><span class="p">]</span>
    <span class="n">leoAst</span><span class="o">.</span><span class="n">py</span> <span class="o">--</span><span class="n">unittest</span> <span class="p">[</span><span class="n">ARGS</span><span class="p">]</span>

<span class="n">examples</span><span class="p">:</span>
    <span class="o">--</span><span class="n">py</span><span class="o">-</span><span class="n">cov</span> <span class="s2">&quot;-f TestOrange&quot;</span>
    <span class="o">--</span><span class="n">pytest</span> <span class="s2">&quot;-f TestOrange&quot;</span>
    <span class="o">--</span><span class="n">unittest</span> <span class="n">TestOrange</span>

<span class="n">positional</span> <span class="n">arguments</span><span class="p">:</span>
  <span class="n">PATHS</span>              <span class="n">directory</span> <span class="ow">or</span> <span class="nb">list</span> <span class="n">of</span> <span class="n">files</span>

<span class="n">optional</span> <span class="n">arguments</span><span class="p">:</span>
  <span class="o">-</span><span class="n">h</span><span class="p">,</span> <span class="o">--</span><span class="n">help</span>         <span class="n">show</span> <span class="n">this</span> <span class="n">help</span> <span class="n">message</span> <span class="ow">and</span> <span class="n">exit</span>
  <span class="o">--</span><span class="n">fstringify</span>       <span class="n">leonine</span> <span class="n">fstringify</span>
  <span class="o">--</span><span class="n">fstringify</span><span class="o">-</span><span class="n">diff</span>  <span class="n">show</span> <span class="n">fstringify</span> <span class="n">diff</span>
  <span class="o">--</span><span class="n">orange</span>           <span class="n">leonine</span> <span class="n">Black</span>
  <span class="o">--</span><span class="n">orange</span><span class="o">-</span><span class="n">diff</span>      <span class="n">show</span> <span class="n">orange</span> <span class="n">diff</span>
  <span class="o">--</span><span class="n">py</span><span class="o">-</span><span class="n">cov</span>           <span class="n">run</span> <span class="n">pytest</span> <span class="o">--</span><span class="n">cov</span> <span class="n">on</span> <span class="n">leoAst</span><span class="o">.</span><span class="n">py</span>
  <span class="o">--</span><span class="n">pytest</span>           <span class="n">run</span> <span class="n">pytest</span> <span class="n">on</span> <span class="n">leoAst</span><span class="o">.</span><span class="n">py</span>
  <span class="o">--</span><span class="n">unittest</span>         <span class="n">run</span> <span class="n">unittest</span> <span class="n">on</span> <span class="n">leoAst</span><span class="o">.</span><span class="n">py</span>
</pre></div>
</div>
</section>
<section id="running-the-code-python-programmatically">
<h4><a class="toc-backref" href="#id9">Running the code python programmatically</a><a class="headerlink" href="#running-the-code-python-programmatically" title="Permalink to this heading">¶</a></h4>
<p>To access the code, do one of the following:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">leoAst</span>
<span class="kn">import</span> <span class="nn">leo.core.leoAst</span> <span class="k">as</span> <span class="nn">leoAst</span>
</pre></div>
</div>
<p>You can then run the fstringify commands as follows:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">changed</span> <span class="o">=</span> <span class="n">leoAst</span><span class="o">.</span><span class="n">Fstringify</span><span class="p">()</span><span class="o">.</span><span class="n">fstringify_file</span><span class="p">(</span><span class="n">filename</span><span class="p">)</span>
<span class="n">changed</span> <span class="o">=</span> <span class="n">leoAst</span><span class="o">.</span><span class="n">Fstringify</span><span class="p">()</span><span class="o">.</span><span class="n">fstringify_diff_files</span><span class="p">(</span><span class="n">filename</span><span class="p">)</span>
</pre></div>
</div>
</section>
<section id="running-unit-tests-and-coverage-tests-programmatically">
<h4><a class="toc-backref" href="#id10">Running unit tests and coverage tests programmatically</a><a class="headerlink" href="#running-unit-tests-and-coverage-tests-programmatically" title="Permalink to this heading">¶</a></h4>
<p>The following runs all unit tests for leoAst.py:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">python</span> <span class="o">-</span><span class="n">m</span> <span class="n">leo</span><span class="o">.</span><span class="n">core</span><span class="o">.</span><span class="n">leoAst</span>
</pre></div>
</div>
<p>The following runs coverage tests:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">pytest</span> <span class="o">-</span><span class="n">x</span> <span class="o">--</span><span class="n">cov</span><span class="o">-</span><span class="n">report</span> <span class="n">html</span> <span class="o">--</span><span class="n">cov</span><span class="o">-</span><span class="n">report</span> <span class="n">term</span><span class="o">-</span><span class="n">missing</span> <span class="o">--</span><span class="n">cov</span><span class="o">=</span><span class="n">leo</span><span class="o">.</span><span class="n">core</span><span class="o">.</span><span class="n">leoAst</span> <span class="n">leo</span><span class="o">/</span><span class="n">core</span><span class="o">/</span><span class="n">leoAst</span><span class="o">.</span><span class="n">py</span>
</pre></div>
</div>
</section>
</section>
<section id="tokenorder-classes-theory-of-operation">
<h3><a class="toc-backref" href="#id11">TokenOrder classes: Theory of operation</a><a class="headerlink" href="#tokenorder-classes-theory-of-operation" title="Permalink to this heading">¶</a></h3>
<p>This is the Theory of Operation for the TokenOrderGenerator (TOG) class and
related classes.</p>
<section id="token-order-classes">
<h4><a class="toc-backref" href="#id12">Token-order classes</a><a class="headerlink" href="#token-order-classes" title="Permalink to this heading">¶</a></h4>
<p>The <strong>TokenOrderGenerator</strong> (TOG) class injects two-way links between all
tokens and the corresponding ast nodes. The TOG class also injects
parent/child links into all ast nodes.</p>
<p>The TOG class defines generators that visit ast nodes in <strong>token order</strong>,
the traversal order that corresponds to the order of the tokens produced by
python’s tokenizer module. The only way to ensure this correspondence is to
use separate visitors for all ast nodes. All visitors are straightforward
generators.</p>
<p>TOG visitors <cite>yield from</cite> tog.gen* generators to visit subtrees. All such
generators eventually call TOG.sync_token, which checks that that tokens
are, in fact, visited in the correct order. TOG.sync_token is an
ever-present unit test.</p>
<p>The <strong>TokenOrderTraversal</strong> (TOT) class uses the parent/child links created
by the TOG class. TOT.traverse contains a single for-loop that calls all
nodes of the parse tree in token order. This loop is extremely fast. Using
the TOT class, client code can easily modify the token list or parse tree
as desired.</p>
</section>
<section id="other-classes">
<h4><a class="toc-backref" href="#id13">Other classes</a><a class="headerlink" href="#other-classes" title="Permalink to this heading">¶</a></h4>
<p>The <strong>Token</strong> class represents one token, created by tokenize.tokenize.</p>
<p>The <strong>Fstringify</strong> class is an re-implementation of the external fstringify
project using the TOG class.</p>
<p>The <strong>Orange</strong> class is a re-implementation of the black project. <br />
The name “Orange” is a play on words: “Orange is the new black”.</p>
<p>The <strong>AstDumper</strong> class provides an extensive set of tools for examining
token lists, parse trees, and the links between them.</p>
<p>The <strong>BaseTest</strong> class provides common infrastructure for all other test classes.
<em>Important</em>: BaseTest.make_data is, all by itself, a very strong unit test.</p>
</section>
<section id="significant-vs-insignificant-tokens">
<h4><a class="toc-backref" href="#id14">Significant vs insignificant tokens</a><a class="headerlink" href="#significant-vs-insignificant-tokens" title="Permalink to this heading">¶</a></h4>
<p>The distinction between <strong>significant</strong> and <strong>insignificant</strong> tokens is
crucial. Visitors call TOG.gen_token, TOG.gen_op, etc. <em>only</em> for
significant tokens. The <strong>is_significant</strong> and <strong>is_significant_token</strong>
functions define which tokens are significant.</p>
<p>Visitors can’t know, just by looking at the parse tree, whether the input
contains <em>insignificant</em> tokens. For example, the source tokens might
contain non-essential parentheses, or optional trailing commas, or whether
two statements are separated by a semicolon.</p>
</section>
<section id="helping-tog-visitors">
<h4><a class="toc-backref" href="#id15">Helping TOG visitors</a><a class="headerlink" href="#helping-tog-visitors" title="Permalink to this heading">¶</a></h4>
<p>The TOG.do_If visitor calls <strong>TOG.find_next_significant_token</strong> to
determine whether TOG.do_If should generate an “if” or an “elif” token.
This help is essential, because the following two source files generate
identical parse trees!:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">if</span> <span class="mi">1</span><span class="p">:</span>            <span class="k">if</span> <span class="mi">1</span><span class="p">:</span>
    <span class="k">pass</span>             <span class="k">pass</span>
<span class="k">else</span><span class="p">:</span>            <span class="k">elif</span> <span class="mi">2</span><span class="p">:</span>
    <span class="k">if</span> <span class="mi">2</span><span class="p">:</span>            <span class="k">pass</span>
        <span class="k">pass</span>
</pre></div>
</div>
<p>Similarly, the TOG.do_Str and TOG.do_JoinedStr visitors call
<strong>TOG.get_concatenated_string_tokens</strong> to handle one ore more concatenated
string tokens.</p>
<p>Finally, TOG.do_slice calls TOG.find_next_significant_token to determine
whether a slice without a step contains an optional colon.</p>
<p>TOG.find_next_significant_token and TOG.get_concatenated_string_tokens are
crucial inventions. TOG class would not be possible without them.</p>
</section>
<section id="syncing-tokens">
<h4><a class="toc-backref" href="#id16">Syncing tokens</a><a class="headerlink" href="#syncing-tokens" title="Permalink to this heading">¶</a></h4>
<p><strong>TOG.px</strong> is an index into the token list. It is either -1, or it points
at the previous significant token. <em>Note</em>: TOG.find_next_significant_token
and TOG.get_concatenated_string_tokens use TOG.px, but never change TOG.px.</p>
<p>TOG.sync_token(self, kind, val) associates tokens with ast nodes as
follows:</p>
<ol class="arabic simple">
<li><p>If (kind, val) denote an <em>insignificant</em> token, TOG.sync_token does
nothing.</p></li>
<li><p>Otherwise, (kind, val) denotes a <em>significant</em> token. TOG.sync_token
associates that token, <em>plus</em> all previous <em>insignificant</em> tokens with
self.node, the ast node presently being visited.</p></li>
</ol>
<p>In addition, if (kind, val) denotes a <em>significant</em> token, TOG.sync_token
checks that the next <em>significant</em> token in the token list has the expected
kind and value. This is done as follows:</p>
<ul class="simple">
<li><p>TOG.sync_token advances TOG.px to point at the next significant token,
call it T.</p></li>
<li><p>TOG.raises AssignLinksError if (T.kind, T.value) != (kind, val)</p></li>
</ul>
<p>To summarize token syncing:</p>
<ul class="simple">
<li><p>The TOG.px index tracks the last-seen <em>significant</em> token.</p></li>
<li><p>TOG.px advances monotonically through the token list.</p></li>
<li><p>TOG.find_next_significant_token and TOG.get_concatenated_string_tokens
scan forward through the token list using a private copy of TOG.px. These
methods never change TOG.px itself.</p></li>
<li><p>This token-syncing machinery is the <em>simplest</em> thing that could possibly
work. It is also the <em>fastest</em> thing that could possibly work.</p></li>
</ul>
</section>
<section id="figures-of-merit">
<h4><a class="toc-backref" href="#id17">Figures of merit</a><a class="headerlink" href="#figures-of-merit" title="Permalink to this heading">¶</a></h4>
<p><strong>Simplicity</strong>:</p>
<ul class="simple">
<li><p>The distinction between significant and insignificant tokens makes
token-order traversals possible. This distinction drastically simplifies
TOG visitors. They never have to generate insignificant tokens!</p></li>
<li><p>TOG.find_next_significant_token and TOG.get_concatenated_string_tokens()
use TOG.px to look ahead in the token list.</p></li>
<li><p>It took a long time to realize that the parse tree needs help from the
token list, not the other way around!</p></li>
</ul>
<p><strong>Speed</strong>: The TOG creates links between tokens and ast nodes in roughly the time
taken by python’s tokenize.tokenize and ast.parse library methods. The TOT
class traverses trees annotated with parent/child links even more quickly.</p>
<p>TOG class avoids both ast.fix_missing_locations and ast.get_source_segment,
which are too slow to be useful.</p>
<p><strong>Memory</strong>: The TOG class makes no significant demand on python’s resources:</p>
<ul class="simple">
<li><p>Generators add nothing to python’s call stack.</p></li>
<li><p>The <em>only</em> variable-length data created by the TOG is TOG.node_stack.
This stack resides in python’s heap, so its length is unimportant. In the
worst case, it might contain a few thousand entries.</p></li>
<li><p>The TOT uses no variable-length data whatever.</p></li>
</ul>
</section>
</section>
<section id="notable-functions-methods">
<h3><a class="toc-backref" href="#id18">Notable functions &amp; methods</a><a class="headerlink" href="#notable-functions-methods" title="Permalink to this heading">¶</a></h3>
<section id="initing-data-structures">
<h4><a class="toc-backref" href="#id19">Initing data structures</a><a class="headerlink" href="#initing-data-structures" title="Permalink to this heading">¶</a></h4>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">make_tokens</span><span class="p">(</span><span class="n">contents</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Return a list (not a generator) of Token objects corresponding to the</span>
<span class="sd">    list of 5-tuples generated by tokenize.tokenize.</span>
<span class="sd">    &quot;&quot;&quot;</span>

<span class="k">def</span> <span class="nf">nearest_common_ancestor</span><span class="p">(</span><span class="n">node1</span><span class="p">,</span> <span class="n">node2</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Return the nearest common ancestor nodes for the given nodes.</span>

<span class="sd">    The nodes must have parent links.</span>
<span class="sd">    &quot;&quot;&quot;</span>

<span class="k">def</span> <span class="nf">parse_ast</span><span class="p">(</span><span class="n">s</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Parse string s, catching &amp; reporting all exceptions.</span>
<span class="sd">    Return the ast node, or None.</span>
<span class="sd">    &quot;&quot;&quot;</span>

<span class="k">def</span> <span class="nf">tokens_for_node</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">tokens</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;Return the list of all tokens descending from node.&quot;&quot;&quot;</span>
</pre></div>
</div>
</section>
<section id="reading-writing-files">
<h4><a class="toc-backref" href="#id20">Reading &amp; writing files</a><a class="headerlink" href="#reading-writing-files" title="Permalink to this heading">¶</a></h4>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">read_file_with_encoding</span><span class="p">(</span><span class="n">filename</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Read the file, returning (e, s).</span>

<span class="sd">    s is the string, converted to unicode, or None if there was an error.</span>

<span class="sd">    e is the encoding of s, computed in the following order:</span>

<span class="sd">    - The BOM encoding if the file starts with a BOM mark.</span>
<span class="sd">    - The encoding given in the # -*- coding: utf-8 -*- line.</span>
<span class="sd">    - The encoding given by the &#39;encoding&#39; keyword arg. - &#39;utf-8&#39;.</span>
<span class="sd">    &quot;&quot;&quot;</span>

<span class="k">def</span> <span class="nf">write_file</span><span class="p">(</span><span class="n">filename</span><span class="p">,</span> <span class="n">s</span><span class="p">,</span> <span class="n">encoding</span><span class="o">=</span><span class="s1">&#39;utf-8&#39;</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;Write the string s to the file whose name is given.&quot;&quot;&quot;</span>
</pre></div>
</div>
</section>
<section id="reports">
<h4><a class="toc-backref" href="#id21">Reports</a><a class="headerlink" href="#reports" title="Permalink to this heading">¶</a></h4>
<p>The dump_* functions pretty-print tokens and parse trees in various
formats:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">show_diffs</span><span class="p">(</span><span class="n">s1</span><span class="p">,</span> <span class="n">s2</span><span class="p">,</span> <span class="n">filename</span><span class="o">=</span><span class="s1">&#39;&#39;</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;Print diffs between strings s1 and s2.&quot;&quot;&quot;</span>

<span class="k">def</span> <span class="nf">tokens_to_string</span><span class="p">(</span><span class="n">tokens</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;Return the string represented by the list of tokens.&quot;&quot;&quot;</span>
</pre></div>
</div>
</section>
<section id="updating-tokens-and-parse-trees">
<h4><a class="toc-backref" href="#id22">Updating tokens and parse trees</a><a class="headerlink" href="#updating-tokens-and-parse-trees" title="Permalink to this heading">¶</a></h4>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">add_token_to_token_list</span><span class="p">(</span><span class="n">token</span><span class="p">,</span> <span class="n">node</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;Insert token in the proper location of node.token_list.&quot;&quot;&quot;</span>

<span class="k">def</span> <span class="nf">replace_node</span><span class="p">(</span><span class="n">new_node</span><span class="p">,</span> <span class="n">old_node</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;Replace new_node by old_node in the parse tree.&quot;&quot;&quot;</span>

<span class="k">def</span> <span class="nf">replace_token</span><span class="p">(</span><span class="n">token</span><span class="p">,</span> <span class="n">kind</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;Replace kind and value of the given token.&quot;&quot;&quot;</span>
</pre></div>
</div>
</section>
<section id="tokenordergenerator-init-from-file">
<h4><a class="toc-backref" href="#id23">TokenOrderGenerator.init_from_file</a><a class="headerlink" href="#tokenordergenerator-init-from-file" title="Permalink to this heading">¶</a></h4>
<p>This method creates the tokens list and the parse tree and adds all links
between tokens and parse tree nodes:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">init_from_file</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">filename</span><span class="p">):</span>
<span class="w">    </span><span class="sd">&quot;&quot;&quot;</span>
<span class="sd">    Create the tokens and ast tree for the given file.</span>

<span class="sd">    Return (contents, encoding, tokens, tree).</span>
<span class="sd">    &quot;&quot;&quot;</span>
    <span class="bp">self</span><span class="o">.</span><span class="n">level</span> <span class="o">=</span> <span class="mi">0</span>
    <span class="bp">self</span><span class="o">.</span><span class="n">filename</span> <span class="o">=</span> <span class="n">filename</span>
    <span class="n">encoding</span><span class="p">,</span> <span class="n">contents</span> <span class="o">=</span> <span class="n">read_file_with_encoding</span><span class="p">(</span><span class="n">filename</span><span class="p">)</span>
    <span class="k">if</span> <span class="n">contents</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
        <span class="k">return</span> <span class="kc">None</span><span class="p">,</span> <span class="kc">None</span><span class="p">,</span> <span class="kc">None</span><span class="p">,</span> <span class="kc">None</span>
    <span class="bp">self</span><span class="o">.</span><span class="n">tokens</span> <span class="o">=</span> <span class="n">tokens</span> <span class="o">=</span> <span class="n">make_tokens</span><span class="p">(</span><span class="n">contents</span><span class="p">)</span>
    <span class="bp">self</span><span class="o">.</span><span class="n">tree</span> <span class="o">=</span> <span class="n">tree</span> <span class="o">=</span> <span class="n">parse_ast</span><span class="p">(</span><span class="n">contents</span><span class="p">)</span>
    <span class="bp">self</span><span class="o">.</span><span class="n">create_links</span><span class="p">(</span><span class="n">tokens</span><span class="p">,</span> <span class="n">tree</span><span class="p">)</span>
    <span class="bp">self</span><span class="o">.</span><span class="n">reassign_tokens</span><span class="p">(</span><span class="n">tokens</span><span class="p">,</span> <span class="n">tree</span><span class="p">)</span>
    <span class="k">return</span> <span class="n">contents</span><span class="p">,</span> <span class="n">encoding</span><span class="p">,</span> <span class="n">tokens</span><span class="p">,</span> <span class="n">tree</span>
</pre></div>
</div>
</section>
</section>
<section id="maintaining-leoast-py">
<h3><a class="toc-backref" href="#id24">Maintaining leoAst.py</a><a class="headerlink" href="#maintaining-leoast-py" title="Permalink to this heading">¶</a></h3>
<p>New ast nodes are sometimes required to support new language features, especially language features that require new syntax or keywords. Python has added new nodes fairly often in the past. New nodes may be added in future. When that happens, the following changes will be needed to leoAst.py:</p>
<ul class="simple">
<li><p>Add a visitor for the new node.</p></li>
<li><p>Add one or more unit tests that fully cover the new visitor.</p></li>
</ul>
<p>The test_visitors_exist unit test checks that visitors exist for all ast nodes defined by to a particular version of python.</p>
<p>See <a class="reference external" href="https://github.com/leo-editor/leo-editor/issues/1440">Leo issue #1440</a> for notes relating to the code.</p>
</section>
</section>
<section id="unicode-reference">
<h2><a class="toc-backref" href="#id25">Unicode reference</a><a class="headerlink" href="#unicode-reference" title="Permalink to this heading">¶</a></h2>
<p>Leo uses unicode internally for all strings.</p>
<ol class="arabic">
<li><p>Leo converts headline and body text to unicode when reading .leo files and external files. Both .leo files and external files may specify their encoding.  The default is utf-8. If the encoding used in a external file is not “utf-8” it is represented in the &#64;+leo sentinel line. For example:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>    <span class="c1">#@+leo-encoding=iso-8859-1.</span>

<span class="n">The</span> <span class="n">utf</span><span class="o">-</span><span class="mi">8</span> <span class="n">encoding</span> <span class="ow">is</span> <span class="n">a</span> <span class="s2">&quot;lossless&quot;</span> <span class="n">encoding</span> <span class="p">(</span><span class="n">it</span> <span class="n">can</span> <span class="n">represent</span> <span class="nb">all</span>
<span class="n">unicode</span> <span class="n">code</span> <span class="n">points</span><span class="p">),</span> <span class="n">so</span> <span class="n">converting</span> <span class="n">to</span> <span class="ow">and</span> <span class="kn">from</span> <span class="nn">utf</span><span class="o">-</span><span class="mi">8</span> <span class="n">plain</span>
<span class="n">strings</span> <span class="n">will</span> <span class="n">never</span> <span class="n">cause</span> <span class="n">a</span> <span class="n">problem</span><span class="o">.</span> <span class="n">When</span> <span class="n">reading</span> <span class="ow">or</span> <span class="n">writing</span> <span class="n">a</span>
<span class="n">character</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">a</span> <span class="s2">&quot;lossy&quot;</span> <span class="n">encoding</span><span class="p">,</span> <span class="n">Leo</span> <span class="n">converts</span> <span class="n">such</span> <span class="n">characters</span>
<span class="n">to</span> <span class="s1">&#39;?&#39;</span> <span class="ow">and</span> <span class="n">issues</span> <span class="n">a</span> <span class="n">warning</span><span class="o">.</span>
</pre></div>
</div>
</li>
<li><p>When writing .leo files and external files Leo uses the same encoding used to read the file, again with utf-8 used as a default.</p></li>
<li><p>leoSettings.leo contains the following Unicode settings, with the defaults as shown:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>    <span class="n">default_derived_file_encoding</span> <span class="o">=</span> <span class="n">UTF</span><span class="o">-</span><span class="mi">8</span>
    <span class="n">new_leo_file_encoding</span> <span class="o">=</span> <span class="n">UTF</span><span class="o">-</span><span class="mi">8</span>

<span class="n">These</span> <span class="n">control</span> <span class="n">the</span> <span class="n">default</span> <span class="n">encodings</span> <span class="n">used</span> <span class="n">when</span> <span class="n">writing</span> <span class="n">external</span>
<span class="n">files</span> <span class="ow">and</span> <span class="o">.</span><span class="n">leo</span> <span class="n">files</span><span class="o">.</span> <span class="n">Changing</span> <span class="n">the</span> <span class="n">new_leo_file_encoding</span> <span class="n">setting</span>
<span class="ow">is</span> <span class="ow">not</span> <span class="n">recommended</span><span class="o">.</span> <span class="n">See</span> <span class="n">the</span> <span class="n">comments</span> <span class="ow">in</span> <span class="n">leoSettings</span><span class="o">.</span><span class="n">leo</span><span class="o">.</span> <span class="n">You</span> <span class="n">may</span>
<span class="nb">set</span> <span class="n">default_derived_file_encoding</span> <span class="n">to</span> <span class="n">anything</span> <span class="n">that</span> <span class="n">makes</span> <span class="n">sense</span> <span class="k">for</span>
<span class="n">you</span><span class="o">.</span>
</pre></div>
</div>
</li>
<li><p>The &#64;encoding directive specifies the encoding used in a external file. You can’t mix encodings in a single external file.</p></li>
</ol>
</section>
<section id="valid-url-s">
<h2><a class="toc-backref" href="#id26">Valid URL’s</a><a class="headerlink" href="#valid-url-s" title="Permalink to this heading">¶</a></h2>
<p>Leo checks that the URL is valid before attempting to open it. A valid URL is:</p>
<ul class="simple">
<li><p>3 or more lowercase alphas</p></li>
<li><p>followed by one :</p></li>
<li><p>followed by one or more of:</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">$%&amp;'()*+,-./0-9:=?&#64;A-Z_a-z{}~</span></code></p></li>
<li><p>followed by one of: <code class="docutils literal notranslate"><span class="pre">$%&amp;'()*+/0-9:=?&#64;A-Z_a-z}~</span></code></p></li>
</ul>
<p>That is, a comma, hyphen and open curly brace may not be the last character.</p>
<p>URL’s in Leo should contain no spaces: use %20 to indicate spaces.</p>
<p>You may use any type of URL that your browser supports: http, mailto, ftp, file, etc.</p>
</section>
<section id="the-mulder-ream-update-algorithm">
<h2><a class="toc-backref" href="#id27">The Mulder/Ream update algorithm</a><a class="headerlink" href="#the-mulder-ream-update-algorithm" title="Permalink to this heading">¶</a></h2>
<p>This appendix documents the Mulder/Ream update algorithm in detail, with an informal proof of its correctness.</p>
<p>Prior to Leo 5.1, Leo used Bernhard Mulder’s original algorithm to read &#64;shadow files. Starting with Leo 5.1, Leo uses this algorithm to read both &#64;clean and &#64;shadow files. Conceptually, both algorithms work as described in the next section.</p>
<p>In February 2015 EKR realized that the &#64;shadow algorithm could be used to update &#64;clean (&#64;nosent) files. Simplifying the algorithm instantly became a top priority. The new code emerged several days later, made possible by the x.sentinels array. It is an important milestone in Leo’s history.</p>
<section id="what-the-algorithm-does">
<h3><a class="toc-backref" href="#id28">What the algorithm does</a><a class="headerlink" href="#what-the-algorithm-does" title="Permalink to this heading">¶</a></h3>
<p>For simplicity, this discussion will assume that we are updating an
external file, x, created with &#64;clean x. The update algorithm works
exactly the same way with &#64;shadow trees.</p>
<p>The algorithm works with <em>any</em> kind of text file. The algorithm uses only
difflib. It knows nothing about the text or its meaning. No parsing is ever
done.</p>
<p>Suppose file x has been changed outside of Leo. When Leo reads x it does
the following:</p>
<ol class="arabic">
<li><p>Recreates the <em>old</em> version of x <em>without</em> sentinels by writing the
&#64;clean x <em>outline</em> into a string, as if it were writing the &#64;clean x
outline again.</p></li>
<li><p>Recreates all the lines of x <em>with</em> sentinels by writing the &#64;clean x
<em>outline</em> into a string, as if it was writing an &#64;file node! Let’s call
these lines the <strong>old sentinels</strong> lines.</p></li>
<li><p>Uses difflib.SequenceMatcher to create a set of diffs between the
old and new versions of x <em>without</em> sentinels.</p>
<p><strong>Terminology</strong>: the diffs tell how to change file a into file b. The
actual code uses this terminology: <strong>a</strong> is set of lines in the old
version of x, <strong>b</strong> is the set of lines in the new version of x.</p>
</li>
<li><p>Creates a set of lines, the <strong>new sentinels lines</strong> using the old
sentinels lines, the a and b lines and the diffs.</p>
<p>This is the magic. Bernhard Mulder’s genius was conceiving that a
three-way merge of lines could produce the new outline, <em>with</em>
sentinels. The code is in x.propagate_changed_lines and its helpers.</p>
</li>
<li><p>Replaces the &#64;clean tree with the new tree created by reading the new
sentinels lines with the &#64;file read logic.</p></li>
</ol>
<p><strong>Important</strong>: The update algorithm never changes sentinels. It never
inserts or deletes nodes. The user is responsible for creating nodes to
hold new lines, or for deleting nodes that become empty as the result of
deleting lines.</p>
</section>
<section id="guesses-don-t-matter">
<h3><a class="toc-backref" href="#id29">Guesses don’t matter</a><a class="headerlink" href="#guesses-don-t-matter" title="Permalink to this heading">¶</a></h3>
<p>There are several boundary cases that the update algorithm can not resolve.
For example, if a line is inserted between nodes, the algorithm can not
determine whether the line should be inserted at the end of one node or the
start of the next node. Let us call such lines <strong>ambiguous lines</strong>.</p>
<p>The algorithm <em>guesses</em> that ambiguous lines belongs at the end of a node
rather than at the start of the next node. This is usually what is
wanted–we usually insert lines at the end of a node.</p>
<p>Happily, <strong>guesses don’t matter</strong>, for the following reasons:</p>
<ol class="arabic simple">
<li><p>The external file that results from writing the &#64;clean x tree will be
the same as the updated external file <em>no matter where</em> ambiguous lines
are placed. In other words, the update algorithm is <strong>sound</strong>.</p></li>
<li><p>Leo reports nodes that were changed when reading any external file. The
user can review changes to &#64;clean and &#64;file trees in the same way.</p></li>
<li><p>The user can permanently correct any mistaken guess. Guesses only happen
for <em>newly inserted or changed</em> lines. Moving an ambiguous line to the
following node will not change the external file. As a result, the
next time Leo reads the file the line will be placed in the correct node!</p></li>
</ol>
<p>This proves that &#64;shadow and &#64;clean are easy and safe to use. The
remaining sections of this document discuss code-level details.</p>
</section>
<section id="background-of-the-code">
<h3><a class="toc-backref" href="#id30">Background of the code</a><a class="headerlink" href="#background-of-the-code" title="Permalink to this heading">¶</a></h3>
<p>The algorithm depends on three simple, guaranteed, properties of
SequenceMatcher.opcodes. See
<a class="reference external" href="https://docs.python.org/2/library/difflib.html#sequencematcher-examples">https://docs.python.org/2/library/difflib.html#sequencematcher-examples</a></p>
<p><strong>Fact 1</strong>: The opcodes tell how to turn x.a (a list of lines) into x.b
(another list of lines).</p>
<p>The code uses the a and b terminology. It’s concise and easy to remember.</p>
<p><strong>Fact 2</strong>: The opcode indices ai, aj, bi, bj <em>never</em> change because
neither x.a nor x.b changes.</p>
<p>Plain lines of the result can be built up by copying lines from x.b to x.results:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="s1">&#39;replace&#39;</span>   <span class="n">x</span><span class="o">.</span><span class="n">results</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">x</span><span class="o">.</span><span class="n">b</span><span class="p">[</span><span class="n">b1</span><span class="p">:</span><span class="n">b2</span><span class="p">])</span>
<span class="s1">&#39;delete&#39;</span>    <span class="n">do</span> <span class="n">nothing</span>  <span class="p">(</span><span class="n">b1</span> <span class="o">==</span> <span class="n">b2</span><span class="p">)</span>
<span class="s1">&#39;insert&#39;</span>    <span class="n">x</span><span class="o">.</span><span class="n">results</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">x</span><span class="o">.</span><span class="n">b</span><span class="p">[</span><span class="n">b1</span><span class="p">:</span><span class="n">b2</span><span class="p">])</span>
<span class="s1">&#39;equal&#39;</span>     <span class="n">x</span><span class="o">.</span><span class="n">results</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">x</span><span class="o">.</span><span class="n">b</span><span class="p">[</span><span class="n">b1</span><span class="p">:</span><span class="n">b2</span><span class="p">])</span>
</pre></div>
</div>
<p><strong>Fact 3</strong>: The opcodes <em>cover</em> both x.a and x.b, in order, without any gaps.</p>
<p>This is an explicit requirement of sm.get_opcode:</p>
<ul class="simple">
<li><p>The first tuple has ai==aj==bi==bj==0.</p></li>
<li><p>Remaining tuples have ai == (aj from the preceding tuple) and bi == (bj
from the previous tuple).</p></li>
</ul>
<p>Keep in mind this crucial picture:</p>
<ul class="simple">
<li><p>The slices x.a[ai:aj] cover the x.a array, in order without gaps.</p></li>
<li><p>The slices x.b[bi:bj] cover the x.b array, in order without gaps.</p></li>
</ul>
</section>
<section id="aha-the-x-sentinels-array">
<h3><a class="toc-backref" href="#id31">Aha: the x.sentinels array</a><a class="headerlink" href="#aha-the-x-sentinels-array" title="Permalink to this heading">¶</a></h3>
<p>Mulder’s original algorithm was hard to understand or to change. The
culprit was the x.mapping array, which mapped indices into arrays of lines
<em>with</em> sentinels to indices into arrays of lines <em>without</em> sentinels.</p>
<p>The new algorithm replaces the x.mapping array with the x.sentinels array.
As a result, diff indices never need to be adjusted and handling diff
opcodes is easy.</p>
<p>For any index i, x.sentinels[i] is the (possibly empty) list of sentinel
lines that precede line a[i]. Computing x.sentinels from old_private_lines
is easy. Crucially, x.a and x.sentinels are <em>parallel arrays</em>. That is,
len(x.a) == len(x.sentinels), so indices into x.a are <em>also</em> indices into
x.sentinels.</p>
</section>
<section id="strategy-proof-of-correctness">
<h3><a class="toc-backref" href="#id32">Strategy &amp; proof of correctness</a><a class="headerlink" href="#strategy-proof-of-correctness" title="Permalink to this heading">¶</a></h3>
<p>Given the x.sentinels array, the strategy for creating the results is
simple. Given indices ai, aj, bi, bj from an opcode, the algorithm:</p>
<ul class="simple">
<li><p>Writes sentinels from x.sentinels[i], for i in range(ai,aj).</p></li>
<li><p>Writes plain lines from b[i], for i in range(bi,bj).</p></li>
</ul>
<p>This “just works” because the indices cover both a and b.</p>
<ul class="simple">
<li><p>The algorithm writes sentinels exactly once (in order) because each
sentinel appears in x.sentinels[i] for some i in range(len(x.a)).</p></li>
<li><p>The algorithm writes plain lines exactly once (in order) because
each plain line appears in x.b[i] for some i in range(len(x.b)).</p></li>
</ul>
<p>This completes an informal proof of the correctness of the algorithm.</p>
<p>The leading and trailing sentinels lines are easy special cases. This
code, appearing before the main loop, ensures that leading lines are
written first, and only once:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">x</span><span class="o">.</span><span class="n">put_sentinels</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="n">x</span><span class="o">.</span><span class="n">sentinels</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="p">[]</span>
</pre></div>
</div>
<p>Similarly, this line, at the end of the main loop, writes trailing
sentinels:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">x</span><span class="o">.</span><span class="n">results</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">x</span><span class="o">.</span><span class="n">trailing_sentinels</span><span class="p">)</span>
</pre></div>
</div>
</section>
<section id="summary">
<h3><a class="toc-backref" href="#id33">Summary</a><a class="headerlink" href="#summary" title="Permalink to this heading">¶</a></h3>
<p>The algorithm creates an updated set of lines <em>with</em> sentinels using the
&#64;clean outline and the updated external file. These new lines then replace
the original &#64;clean with a new &#64;clean tree. The algorithm uses only
difflib. It will work with <em>any</em> kind of text file. No knowledge of any
language is needed.</p>
<p>The algorithm depends on simple, guaranteed, properties of indices in
SequenceMatcher opcodes.</p>
<p>The algorithm steps through x.sentinels and x.b, extending x.results
as it goes.</p>
<p>The algorithm gets all needed data directly from opcode indices into
x.sentinels and x.b. Using opcode indices requires neither reader
classes nor auxiliary indices.</p>
<p>The algorithm is simple enough to be understood at first reading. I’ll
remember its details for the rest of my life.</p>
</section>
</section>
<section id="why-i-like-python">
<h2><a class="toc-backref" href="#id34">Why I like Python</a><a class="headerlink" href="#why-i-like-python" title="Permalink to this heading">¶</a></h2>
<p>I wrote this soon after discovering Python in 2001. The conclusions are still valid today.</p>
<p>I’ve known for a while that Python was interesting; I attended a Python conference last year and added Python support to Leo. But last week I got that Python is something truly remarkable. I wanted to convert Leo from wxWindows to wxPython, so I began work on c2py, a Python script that would help convert from C++ syntax to Python. While doing so, I had an Aha experience. Python is more than an incremental improvement over Smalltalk or C++ or objective-C; it is “something completely different”. The rest of this post tries to explain this difference.</p>
<section id="clarity">
<h3><a class="toc-backref" href="#id35">Clarity</a><a class="headerlink" href="#clarity" title="Permalink to this heading">¶</a></h3>
<p>What struck me first as I converted C++ code to Python is how much less blah, blah, blah there is in Python. No braces, no stupid semicolons and most importantly, <em>no declarations</em>. No more pointless distinctions between const, char *, char const *, char * and wxString. No more wondering whether a variable should be signed, unsigned, short or long.</p>
<p>Declarations add clutter, declarations are never obviously right and declarations don’t prevent memory allocation tragedies. Declarations also hinder prototyping. In C++, if I change the type of something I must change all related declarations; this can be a huge and dangerous task. With Python, I can change the type of an object without changing the code at all! It’s no accident that Leo’s new log pane was created first in Python.</p>
<p>Functions returning tuples are a “minor” feature with a huge impact on code clarity. No more passing pointers to data, no more defining (and allocating and deallocating) temporary structs to hold multiple values.</p>
<p>Python can’t check declarations because there aren’t any. However, there is a really nifty tool called <a class="reference external" href="https://pylint.pycqa.org/en/latest/">pylint</a> that does many of the checks typically done by compilers.</p>
</section>
<section id="power">
<h3><a class="toc-backref" href="#id36">Power</a><a class="headerlink" href="#power" title="Permalink to this heading">¶</a></h3>
<p>Python is much more powerful than C++, not because Python has more features, but because Python needs <em>less</em> features. Some examples:</p>
<ul class="simple">
<li><p>Python does everything that the C++ Standard Template Library (STL) does, without any of the blah, blah, blah needed by STL. No fuss, no muss, no code bloat.</p></li>
<li><p>Python’s slicing mechanism is very powerful and applies to any sequence (string, list or tuple). Python’s string library does more with far less functions because slices replace many functions typically found in other string libraries.</p></li>
<li><p>Writing dict = {} creates a dictionary (hash table). Hash tables can contain anything, including lists and other hash tables.</p></li>
<li><p>Python’s special functions,  __init__, __del__, __repr__, __cmp__, etc. are an elegant way to handle any special need that might arise.</p></li>
</ul>
</section>
<section id="safety">
<h3><a class="toc-backref" href="#id37">Safety</a><a class="headerlink" href="#safety" title="Permalink to this heading">¶</a></h3>
<p>Before using Python I never fully realized how difficult and dangerous memory allocation is in C++. Try doing:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">aList</span><span class="p">[</span><span class="n">i</span><span class="p">:</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">aString</span><span class="p">)</span>
</pre></div>
</div>
<p>in C.  You will write about 20 lines of C code. Any error in this code will create a memory allocation crash or leak.</p>
<p>Python is fundamentally safe. C++ is fundamentally unsafe. When I am using Python I am free from worry and anxiety. When I am using C++ I must be constantly “on guard.” A momentary lapse can create a hard-to-find pointer bug. With Python, almost nothing serious can ever go wrong, so I can work late at night, or after a beer. The Python debugger is always available. If an exception occurs, the debugger/interpreter tells me just what went wrong. I don’t have to plan a debugging strategy! Finally, Python recovers from exceptions, so Leo can keep right on going even after a crash!</p>
</section>
<section id="speed">
<h3><a class="toc-backref" href="#id38">Speed</a><a class="headerlink" href="#speed" title="Permalink to this heading">¶</a></h3>
<p>Python has almost all the speed of C. Other interpretive environments such as icon and Smalltalk have clarity, power and safety similar to Python. What makes Python unique is its seamless way of making C code look like Python code. Python executes at essentially the speed of C code because most Python modules are written in C. The overhead in calling such modules is negligible. Moreover, if code is too slow, one can always create a C module to do the job.</p>
<p>In fact, Python encourages optimization by moving to higher levels of expression. For example, Leo’s Open command reads an XML file. If this command is too slow I can use Python’s XML parser module. This will speed up Leo while at the same time raising the level of the code.</p>
</section>
<section id="conclusions">
<h3><a class="toc-backref" href="#id39">Conclusions</a><a class="headerlink" href="#conclusions" title="Permalink to this heading">¶</a></h3>
<p>Little of Python is completely new. What stands out is the superb engineering judgment evident in Python’s design. Python is extremely powerful, yet small, simple and elegant. Python allows me to express my intentions clearly and at the highest possible level.</p>
<p>The only hope of making Leo all it can be is to use the best possible tools. I believe Python will allow me to add, at long last, the new features that Leo should have.</p>
<p>Edward K. Ream, October 25, 2001.  P.S., September, 2005:</p>
<p>Four years of experience have only added to my admiration for Python. Leo could
not possibly be what it is today without Python.</p>
</section>
</section>
</section>


            <div class="clearer"></div>
          </div>
        </div>
      </div>
      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
        <div class="sphinxsidebarwrapper">
            <p class="logo"><a href="leo_toc.html">
              <img class="logo" src="_static/LeoLogo.svg" alt="Logo"/>
            </a></p>
  <div>
    <h4>Previous topic</h4>
    <p class="topless"><a href="leo-university.html"
                          title="previous chapter">Leo University</a></p>
  </div>
  <div>
    <h4>Next topic</h4>
    <p class="topless"><a href="toc-more-links.html"
                          title="next chapter">More Leo Links</a></p>
  </div>
<div id="searchbox" style="display: none" role="search">
  <h3 id="searchlabel">Quick search</h3>
    <div class="searchformwrapper">
    <form class="search" action="search.html" method="get">
      <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
      <input type="submit" value="Go" />
    </form>
    </div>
</div>
<script>document.getElementById('searchbox').style.display = "block"</script>
        </div>
<div id="sidebarbutton" title="Collapse sidebar">
<span>«</span>
</div>

      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="toc-more-links.html" title="More Leo Links"
             >next</a> |</li>
        <li class="right" >
          <a href="leo-university.html" title="Leo University"
             >previous</a> |</li>
        <li class="nav-item nav-item-0"><a href="leo_toc.html">Leo 6.7.2 documentation</a> &#187;</li>
        <li class="nav-item nav-item-this"><a href="">Appendices</a></li> 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &#169; Copyright 1997-2023, Edward K. Ream.
      Last updated on February 28, 2023.
      Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 5.3.0.
    </div>
  </body>
</html>